以局部最優策略為基礎來進行求解～～

白話說就是每一步都選擇當前狀態下的最佳選擇，「希望」但不一定最終能夠達到全局最優解～明天來說說為什麼不一定

• 找零問題（Coin Change Problem）：給定一定的面額和一定的金額，找到使用最少的硬幣來湊出這個金額。
• 背包問題（Knapsack Problem）：在背包問題中，貪心算法可能會提供一個近似的最佳解，但不一定能保證找到全局最優解。
• 活動選擇問題（Activity Selection Problem）：假設你有一個需要在同一時間進行的活動清單，每個活動都有一個開始時間和結束時間，你希望安排盡可能多的活動，使得它們彼此之間不相交。
• 哈夫曼編碼（Huffman Coding）：這是一種用於無失真數據壓縮的貪心算法。
• 最小生成樹（Minimum Spanning Tree）：某些情況下，貪心算法可以用於找到最小生成樹，例如在Prim's Algorithm和Kruskal's Algorithm中。
• 最短路徑問題（Shortest Path Problem）：在某些情況下，一些特殊的情形下，貪心策略也可以用於找到最短路徑。

找零問題（Coin Change Problem）

問題描述：
假設你是一個售貨員，你需要找給客戶一定金額的零錢。你手上有各種面額的硬幣，你想找到一種最少數量的硬幣來湊出這個金額。
舉例：
假如你有面額為 [1, 5, 10, 25] 的硬幣，現在你需要找給客戶 36 美分的零錢。
解決方案：
一個貪心的策略是始終選擇最大面額的硬幣，直到找完為止。在這個例子中，你可以先找一個 25 美分的硬幣，然後再找 10 美分，最後找一個 1 美分的硬幣，共需要三個硬幣。

這種貪心策略在這個案例中是有效的，但需要注意的是，對於一些特定的面額組合，貪心策略可能無法找到最佳解。
這就是貪心算法的一個簡單範例，它可以用於解決一些最佳化問題，但並不總是能夠找到全局最優解。

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

# 測試示例
coins = [1, 5, 10, 25]
amount = 17

result = coin_change(coins, amount)
print(f"最少需要{result}枚硬幣湊成{amount}元")